package NewCoder;

import java.util.ArrayList;

public class BM5 {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return mergeKList(lists,0,lists.size()-1);
    }
    public ListNode mergeKList(ArrayList<ListNode> list,int l, int r){
        if(l==r) return list.get(l);
        if(l>r) return null;
        int mid=(r-l)/2+l;
        return merge(mergeKList(list,l,mid),mergeKList(list,mid+1,r));
    }
    public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null || l2==null ){
            return l1==null?l2:l1;
        }
        ListNode dum=new ListNode(-1);
        ListNode cur=dum;
        while(l1!=null & l2!=null){
            if(l1.val<=l2.val){
                cur.next=l1;
                l1=l1.next;
            }else{
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        cur.next=(l1==null?l2:l1);
        return dum.next;
    }
}
